package special;

import java.util.Arrays;

public class LeeCode_LCP_72 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(supplyWagon(new int[]{1, 3, 1, 5})));
    }
    static class Node{
        int val;
        Node next;
        public Node(int val) {
            this.val = val;
        }
    }
    private static int[] supplyWagon(int[] supplies) {
        int n = supplies.length;
        int[] ans = new int[n / 2];
        Node dummy = new Node(-1);
        Node cur = dummy;
        for (int supply : supplies) {
            cur.next = new Node(supply);
            cur = cur.next;
        }
        for (int j = 0; j < n - n / 2; j++) {
            int min = Integer.MAX_VALUE;
            cur = dummy.next;
            Node minn = dummy;
            while (cur.next != null){
                int sum = cur.val + cur.next.val;
                if (sum < min){
                    min = sum;
                    minn = cur;
                }
                cur = cur.next;
            }
            minn.val = min;
            minn.next = minn.next.next;
        }
        cur = dummy.next;
        int i = 0;
        while (cur != null){
            ans[i] = cur.val;
            cur = cur.next;
            i++;
        }
        return ans;
    }
}
